#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define SIZE 10

int binarySearch(const int *arr, size_t n, int key);
int compare(const void *a, const void *b);
void show_arr(const int *arr, size_t n);
int init_arr(int **arr, size_t *n);
int add_element(int **arr, size_t *n, int key);
int del_element(int **arr, size_t *n, int key);
int mod_element(int **arr, size_t *n, int key, int mod);
void destory(int **arr);

int main() {
  int *arr = NULL;
  size_t nmemb = SIZE;
  init_arr(&arr, &nmemb);
  printf("========== 原数组 ==========\n");
  show_arr(arr, nmemb);
  int element, mod, pos;

  while (1) {
    printf("1：增加元素\n"
           "2：删除元素\n"
           "3:修改元素\n"
           "4:查找元素\n"
           "0:退出\n");
    int ch;
    scanf("%d", &ch);
    if (ch == 0)
      break;
    switch (ch) {
    case 1:
      scanf("%d", &element);
      add_element(&arr, &nmemb, element);
      show_arr(arr, nmemb);
      break;
    case 2:
      scanf("%d", &element);
      if (del_element(&arr, &nmemb, element) == 0) {
        printf("%d Not Found\n", element);
      }
      show_arr(arr, nmemb);
      break;
    case 3:
      scanf("%d %d", &element, &mod);
      if (mod_element(&arr, &nmemb, element, mod) == 0) {
        printf("%d Not Found\n", element);
      }
      show_arr(arr, nmemb);
      break;
    case 4:
      scanf("%d", &element);
      pos = binarySearch(arr, nmemb, element);
      if (arr[pos] == element)
        printf("Found! pos is %d\n", pos);
      else
        printf("Not Found\n");
      show_arr(arr, nmemb);
    }
  }
  destory(&arr);
  return 0;
}

int compare(const void *a, const void *b) { return *(int *)a - *(int *)b; }

int init_arr(int **arr, size_t *n) {
  srand(time(NULL));
  *arr = realloc(*arr, (*n) * sizeof(int));

  if (*arr == NULL)
    return -1;

  for (int i = 0; i < *n; i++) {
    (*arr)[i] = rand() % 101;
  }
  qsort(*arr, *n, sizeof(int), compare);
  return 1;
}

void show_arr(const int *arr, size_t n) {
  for (int i = 0; i < n; i++) {
    printf("%d   ", arr[i]);
  }
  putchar('\n');
}
// 二分查找返回目标的下标，或者第一个大于目标的下标
int binarySearch(const int *arr, size_t n, int key) {
  int left = 0, right = n - 1;

  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == key) {
      return mid;
    } else if (arr[mid] > key) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return left;
}
int add_element(int **p, size_t *n, int key) {
  *p = realloc(*p, (*n + 1) * sizeof(int));
  if (*p == NULL) {
    return -1;
  }
  int pos = binarySearch(*p, *n, key);
  memmove(*p + pos + 1, *p + pos, (*n - pos) * sizeof(int));
  (*p)[pos] = key;
  (*n)++;
  return 1;
}

int del_element(int **arr, size_t *n, int key) {
  int pos = binarySearch(*arr, *n, key);
  if ((*arr)[pos] == key) {
    memmove(*arr + pos, *arr + pos + 1, sizeof(int) * (*n - 1 - pos));
    *arr = realloc(*arr, (*n - 1) * sizeof(int));
    (*n)--;
    return 1;
  } else {
    return 0;
  }
}

int mod_element(int **arr, size_t *n, int key, int mod) {
  int pos = binarySearch(*arr, *n, key);
  if ((*arr)[pos] == key) {
    del_element(arr, n, key);
    add_element(arr, n, mod);
    return 1;
  } else {
    return 0;
  }
}

void destory(int **arr) {
  free(*arr);
  *arr = NULL;
}
